home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / answers / rec / puzzles / archive / geometry / part2 < prev    next >
Text File  |  1993-08-17  |  13KB  |  302 lines
  1. Newsgroups: rec.puzzles,news.answers,rec.answers
  2. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!gatech!europa.eng.gtefsd.com!uunet!questrel!chris
  3. From: chris@questrel.com (Chris Cole)
  4. Subject: rec.puzzles Archive (geometry), part 14 of 35
  5. Message-ID: <puzzles/archive/geometry/part2_745653851@questrel.com>
  6. Followup-To: rec.puzzles
  7. Summary: This is part of an archive of questions
  8.  and answers that may be of interest to
  9.  puzzle enthusiasts.
  10.  Part 1 contains the index to the archive.
  11.  Read the rec.puzzles FAQ for more information.
  12. Sender: chris@questrel.com (Chris Cole)
  13. Reply-To: archive-comment@questrel.com
  14. Organization: Questrel, Inc.
  15. References: <puzzles/archive/Instructions_745653851@questrel.com>
  16. Date: Wed, 18 Aug 1993 06:05:22 GMT
  17. Approved: news-answers-request@MIT.Edu
  18. Expires: Thu, 1 Sep 1994 06:04:11 GMT
  19. Lines: 280
  20. Xref: senator-bedfellow.mit.edu rec.puzzles:25003 news.answers:11523 rec.answers:1923
  21.  
  22. Archive-name: puzzles/archive/geometry/part2
  23. Last-modified: 17 Aug 1993
  24. Version: 4
  25.  
  26.  
  27. ==> geometry/tiling/rectangles.with.squares.p <==
  28. Given two sorts of squares, (axa) and (bxb), what rectangles can be tiled?
  29.  
  30. ==> geometry/tiling/rectangles.with.squares.s <==
  31. A rectangle can be tiled with (axa) and (bxb) squares,   iff
  32.  
  33. (i) gcd(a,b)=1 , and any of the following hold:
  34.  
  35. either:  both sides of the rectangle are multiples of a;
  36.     or:  both sides of the rectangle are multiples of b;
  37.     or:  one side is a multiple of (ab), and the other is any length EXCEPT
  38.          one of a finite number of "bad" lengths: those numbers which are
  39.          NOT positive integer combinations of a & b. { By Sylvester's theorem
  40.          there are (a-1)(b-1)/2 of these, the largest being (a-1)(b-1)-1. }
  41.  
  42. (ii) gcd(a,b) = d . 
  43.      Then merely apply (i) to the problem with a,b replaced
  44.      by a/d, b/d  and the rectangle lengths also divided by d.
  45.      i.e.  all cells must appear in (dxd) subsquares.
  46.  
  47. ------
  48. PROOF
  49. It is clear that (ii) follows from (i), and that simple constructions give
  50. the "if" part of (i). For the "only if" part, we prove that...
  51.  
  52. (S) If one side of the rectangle is not divisible by a, and the other is
  53.     not divisible by b, then the tiling is impossible.
  54.  
  55. The results in (i) follow immediately from (S).
  56.  
  57. To prove (S):  ( Chakraborty-Hoey style ).
  58.                  ~~~~~~~~~~~~~~~~
  59. Let the width of the rectangle be a NON-(a-multiple). Then the number of
  60. bxb squares starting (i.e. top edge) at row 1 must be a NON-a-multiple.
  61. Thus the number of bxb starting at row 2 must BE an a-multiple. Similarly
  62. for the number starting at rows 3,4,...,b . Then the number starting at
  63. row (b+1) must be a NON-a-multiple again.
  64.  
  65. Similarly the number starting at rows (2b+1), (3b+1), (4b+1),... must all be
  66. non-a-multiples. So if the number of rows is NOT a multiple of b, (call it
  67. bx+r), then row (bx+1) must have a NON-a-multiple of bxb squares starting
  68. there, i.e. at least one, and there is no room left to squeeze it in.     [QED]
  69. ----
  70.  
  71. A Rickard-style proof of (S) is    ..BBB....BBWWW...WBBB....BBWWW...W(..etc)
  72.   ~~~~~~~   also possible, by      ..BBB....BBWWW...WBBB....BBWWW...W
  73. coloring the rectangle in          ..BBB....BBWWW...WBBB....BBWWW...W
  74. vertical strips as shown here:       <-  a  ->< b-a ><-  a  ->< b-a >
  75.  
  76. Every square tile covers an a-multiple of black squares. But if the width
  77. is a NON-b-multiple, and the number of rows is a NON-a-multiple, then there
  78. are a NON-a-multiple of black squares in total.    [QED]
  79.  
  80. (Note: the coloring must have 1 column of blacks on the right, and any
  81.  ====     spare columns of whites on the left.)
  82.  
  83. ===================
  84.  
  85. Bill Taylor.            wft@math.canterbury.ac.nz
  86.  
  87. >A Rickard-style proof of (S) is    ..BBB....BBWWW...WBBB....BBWWW...W(..etc)
  88. >  ~~~~~~~   also possible, by      ..BBB....BBWWW...WBBB....BBWWW...W
  89. >coloring the rectangle in          ..BBB....BBWWW...WBBB....BBWWW...W
  90. >vertical strips as shown here:       <-  a  ->< b-a ><-  a  ->< b-a >
  91. >
  92. >Every square tile covers an a-multiple of black squares. But if the width
  93. >is a NON-b-multiple, and the number of rows is a NON-a-multiple, then there
  94. >are a NON-a-multiple of black squares in total.    [QED]
  95. >
  96. >(Note: the coloring must have 1 column of blacks on the right, and any
  97. > ====     spare columns of whites on the left.)
  98.  
  99. This statement of how to position the colouring isn't good enough, I'm
  100. afraid. Take a=4, b=7 and consider e.g. a 19x10 rectangle. Coloured your
  101. way, you get:
  102.  
  103.     BWWWBBBBWWWBBBBWWWB
  104.     BWWWBBBBWWWBBBBWWWB
  105.     :::::::::::::::::::
  106.     BWWWBBBBWWWBBBBWWWB
  107.     BWWWBBBBWWWBBBBWWWB
  108.  
  109. The result has 10*10=100 black squares in it, which *is* a multiple of a=4,
  110. despite the fact that 19 is not a multiple of 7 and 10 is not a multiple of
  111. 4.
  112.  
  113. Of course, there is an alternative offset for the pattern that does give you
  114. the result you want:
  115.  
  116.     WWBBBBWWWBBBBWWWBBB
  117.     WWBBBBWWWBBBBWWWBBB
  118.     :::::::::::::::::::
  119.     WWBBBBWWWBBBBWWWBBB
  120.     WWBBBBWWWBBBBWWWBBB
  121.  
  122. To show this happens in general: because the width of the rectangle is a
  123. non-multiple of b, it is possible to position it on the pattern so that the
  124. leftmost column in the rectangle is white and the column just right of the
  125. right edge of the rectangle is black. Suppose N columns are black with this
  126. positioning. Then the rectangle contains N*H black cells, where H is the
  127. height of the rectangle.
  128.  
  129. If we then shift the rectangle right by one, the number of black columns
  130. increases by 1 and it contains (N+1)*H black cells. The difference between
  131. these two numbers of black cells is H, which is not a multiple of a.
  132. Therefore N*H and (N+1)*H cannot both be multiples of a, and so one of these
  133. two positionings of the pattern will suit your purposes.
  134.  
  135. David Seal
  136. dseal@armltd.co.uk
  137.  
  138. ==> geometry/tiling/scaling.p <==
  139. A given rectangle can be entirely covered (i.e. concealed) by an
  140. appropriate arrangement of 25 disks of unit radius.
  141.  
  142. Can the same rectangle be covered by 100 disks of 1/2 unit radius?
  143.  
  144. ==> geometry/tiling/scaling.s <==
  145. Yes.  The same configuration of circles, when every distance is reduced
  146. by half (including the diameters), will cover a similar rectangle whose
  147. sides are one half of the original one.  The original rectangle is the
  148. union of four such rectangles.
  149.  
  150. ==> geometry/tiling/seven.cubes.p <==
  151. Consider 7 cubes of equal size arranged as follows. Place 5 cubes so
  152. that they form a Swiss cross or a + (plus) (4 cubes on the sides and
  153. 1 in the middle). Now place one cube on top of the middle cube and the
  154. seventh below the middle cube, to effectively form a 3-dimensional
  155. Swiss cross.
  156.  
  157. Can a number of such blocks (of 7 cubes each) be arranged so that they
  158. are able to completely fill up a big cube (say 10 times the size of
  159. the small cubes)? It is all right if these blocks project out of the
  160. big cube, but there should be no holes or gaps.
  161.  
  162. ==> geometry/tiling/seven.cubes.s <==
  163. Let n be a positive integer.  Define the function f from Z^n to Z by
  164. f(x) = x_1+2x_2+3x_3+...+nx_n.  For x in Z^n, say y is a neighbor of x
  165. if y and x differ by one in exactly one coordinate.  Let S(x) be the
  166. set consisting of x and its 2n neighbors.  It is easy to check that
  167. the values of f(y) for y in S(x) are congruent to 0,1,2,...,2n+1 (mod
  168. 2n+1) in some order.  Using this, it is easy to check that every y in
  169. Z^n is a neighbor of one and only one x in Z^n such that f(x) is
  170. congruent to 0 (mod 2n+1).  So Z^n can be tiled by clusters of the
  171. form S(x), where f(x) is congruent to 0 mod 2n+1.
  172.  
  173. ==> geometry/topology/fixed.point.p <==
  174. A man hikes up a mountain, and starts hiking at 2:00 in the afternoon
  175. on a Friday.  He does not hike at the same speed (a constant rate), and
  176. stops every once in a while to look at the view.  He reaches the top in
  177. 4 hours.  After spending the night at the top, he leaves the next day
  178. on the same trail at 2:00 in the afternoon.  Coming down, he doesn't
  179. hike at a constant rate, and stops every once in a while to look at the
  180. view.  It takes him 3 hours to get down the mountain.
  181.  
  182. Q: What is the probability that there exists a point along the trail
  183. that the hiker was at on the same time Friday as Saturday?
  184.  
  185. You can assume that the hiker never backtracked. 
  186.  
  187. ==> geometry/topology/fixed.point.s <==
  188. 100%.  Superimpose the days:  Friday starts walking up at 2:00,
  189. Saturday starts walking down at 2:00.   Since they are on the same
  190. path, they must meet.
  191.  
  192. ==> geometry/touching.blocks.p <==
  193. Can six 1x2x4 blocks be arranged so that each block touches n others, for all n?
  194.  
  195. ==> geometry/touching.blocks.s <==
  196. n=0: 6 separate blocks
  197. n=1: 3 pairs
  198. n=2: 2 threesomes
  199. n=3: a 3x3 grid
  200. n=4: a box (each sides touches the four adjoining sides, but not the opposite)
  201. n=5:
  202.  
  203. Crude ascii:
  204. Front view:                  Side view:
  205.  
  206.          /\  /\               ----- 
  207.         /  \/  \              | | |
  208.        /   /\   \             | | |
  209.       /   /  \   \            | | |
  210.       \  /----\  /         ---|.|.|---
  211.        \/|    |\/          |  | | |  |
  212.       -----------          -----------
  213.       |         |             |   |
  214.       -----------             -----
  215.  
  216. -- 
  217. stein.kulseth@tf.tele.no [X.400] stein.kulseth@nta.no [internet]
  218.  
  219. Place block A onto the x-y plane so that four of its corners are at
  220. (0,0), (0,1), (4,0), (4,1) (I give x and y coordinates only because
  221. the z coordinate will always be obvious).  Place block B so four of
  222. its corners are at (2,1), (2,2), (6,1), (6,2).  Now place block C with
  223. one 4x1 face on the x-y plane with one corner at (0,1) (tangent to
  224. block A) and tangent to block B at (2,1).  Note that the angle between
  225. block A and block C is arctan(1/2), and a corner of block C will be at
  226. a point with approximate coordinates (3.5777, 2.7888).  Call this
  227. point P.
  228.  
  229. Now place an identical configuration of blocks on top of the first
  230. three as follows: block D with corners at (3.4,0.4), (4.4,0.4),
  231. (3.4,4.4), (4.4,4.4), block E with corners at (2.4,2.4), (3.4,2.4),
  232. (2.4,-1.6), (3.4,-1.6), and block F with one corner tangent to D at
  233. (3.4,4.4) and one side tangent to E at (2.4,2.4).
  234.  
  235. If you have been plotting this on graph paper, then the following
  236. will be clear:
  237.  
  238. Every block touches every other in its own layer.  And A and B each
  239. touch D and E, and block C touches F.  Point P falls under block D, so
  240. blocks C and D touch, and by symmetry so do blocks F and A.  And the
  241. edge of block C intersects the edge of block E at (2.4,2.2) so blocks
  242. C and E touch, and by symmetry so do blocks F and B.  Done!
  243.  
  244. -- David Karr (karr@cs.cornell.edu)
  245.  
  246. All the blocks are placed with their 2x4 face UP, although any face up
  247. would have worked, as it turns out.  The blocks are called AAAA BBBB CCCC,
  248. etc.
  249.  
  250.       AAAA
  251.       AAAA /_______
  252.       BBCC \
  253.       BBCC
  254.       BBCC
  255.       BBCC
  256.        /\
  257.        ||
  258.  
  259. The two arrows point to the intersection of AC and BC.
  260.  
  261. Now take block "D" and place the top edge along the diagonal (between the
  262. two arrows) so that the block extends SOUTH EAST of the line.  Likely now
  263. the block does not touch either A or B.  So slide the block towards the
  264. NORTH WEST so that it just touches A and B.  You can now easily place
  265. blocks E and F perpendicular to block "D" so that they both touch all of
  266. ABC.....QED
  267. -- 
  268. Guy Cousineau
  269.  
  270. ==> geometry/trigonometry/euclidean.numbers.p <==
  271. For what numbers x is sin(x) expressible using only integers, +, -, *, / and
  272. square root?
  273.  
  274. ==> geometry/trigonometry/euclidean.numbers.s <==
  275. Numbers generated by +, -, *, /, and sqrt from the integers are the
  276. Euclidean numbers, so called because they are those for which line
  277. segments can be constructed by use of straightedge and compass the
  278. ratio of whose lengths has that value.
  279.  
  280. Using degrees, sin (360*M/N) (where (M,N)=1) is Euclidean if and only
  281. if the regular polygon with N sides can be constructed by straightedge
  282. and compass. This is true if (Gauss) and only if (easier) N is a power
  283. of 2 times the product of different Fermat primes (3, 5, 17, 257, 65537
  284. and probably no more). So sin (3/17) = sin (360/(2^3*3*5*17)) is
  285. Euclidean, for example.
  286.  
  287. Some particular values:
  288.  
  289. sin(54) = (1 + sqrt(5))/4  
  290. sin(3) = sqrt(8 - sqrt(3) - sqrt(15) - sqrt(10 - 2*sqrt(5)))/4
  291.  
  292. ==> geometry/trigonometry/inequality.p <==
  293. Show that (sin x)^(sin x) < (cos x)^(cos x) when 0 < x < pi/4.
  294.  
  295. ==> geometry/trigonometry/inequality.s <==
  296. The function f(x) = x^(1/sqrt(1-x^2)) is monotonically increasing for
  297. 0 < x < 1, easily verified by taking the derivative. 
  298. Since 0 < sin x < cos x < 1 for 0 < x < pi/4, f(sin x) < f(cos x).
  299. But f(sin x) = (sin x)^(1/cos x) and f(cos x) = (cos x)^(1/sin x).
  300. Raising both sides to the power (cos x.sin x), we get the desired
  301. result.
  302.